package cn.kevenpotter.leetcode.easy.e1122;

import java.util.*;

public class RelativeSortArray {

    public static void main(String[] args) {
        System.out.println(Arrays.toString(relativeSortArray(new int[]{2, 3, 1, 3, 2, 4, 6, 7, 9, 2, 19}, new int[]{2, 1, 4, 3, 9, 6})));
    }

    public static int[] relativeSortArray(int[] arr1, int[] arr2) {
        Arrays.sort(arr1);
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int num : arr1) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        Queue<Integer> stack = new LinkedList<Integer>();
        for (int num : arr2) {
            if (map.containsKey(num)) {
                for (int i = 0; i < map.get(num); i++) {
                    stack.add(num);
                    if (i + 1 == map.get(num)) map.put(num, -1);
                }
            }
        }
        for (int num : arr1) {
            if (map.get(num) > 0) {
                stack.add(num);
            }
        }
        for (int i = 0; i < arr1.length; i++) {
            arr1[i] = stack.poll();
            if (stack.isEmpty()) break;
        }
        return arr1;
    }
}
